#include<iostream>
#include<vector>
using namespace std;
/*
01背包问题，给一个背包的容量，和一个物品重量数组和价值数组，要求背包能装下物品的最大价值
dp数组的含义，dp[i][j]表示的是任取i个物品放入容量为j的背包中的最大价值
且有递推式dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
递推公式的含义是，任取i个物品放入背包容量为j的背包中的最大价值为背包中放入第i个物品的最大价值和与不放入第i个物品的最大价值
中的最大值
*/
int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int dp(vector<int> weight,vector<int> value,int number,int size)
{
    //初始化dp数组
    vector<vector<int>> dp(number,vector<int>(size+1));
    //先初始化dp数组的第0列（背包重量为0的一列）
    for(int i = 0;i<number;i++)
        dp[i][0] = 0;
    //然后再初始化dp数组的第一行（背包中任取1个物品时的最大重量）
    for(int i = weight[0];i<=size;i++)
        dp[0][i] = value[0];
    //遍历剩下的dp数组，从第二行第二列开始
    for(int i=1;i<number;i++)
    {
        for(int j=1;j<=size;j++)
        {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
        }
    }
    return dp[number-1][size];
}
int main()
{
    cout<<"enter a number of things:"<<endl;
    int number;
    cin>>number;
    cout<<"enter a weight:"<<endl;
    vector<int> weight(number);
    for(int i=0;i<number;i++)
    {
        cin>>weight[i];
    }
    cout<<"enter a value:"<<endl;
    vector<int> value(number);
    for(int i=0;i<number;i++)
    {
        cin>>value[i];
    }
    cout<<"enter size of bag:"<<endl;
    int size;
    cin>>size;
    cout<<"the max value is:"<<dp(weight, value, number, size)<<endl;;
    return 0;
}